Go 中的 Map 设计原理

前言

map 的任务是设计一种数据结构用来维护一个集合的数据，同时需要对该集合进行增删查改的操作。最主要的数据结构有两种：

哈希查找表（Hash table），哈希表实现的 map 或者 set 查找的时间复杂度是O(1)，哈希表优点是查找非常快，哈希表的缺点是失去了数据的顺序性
搜索树（Search tree），平衡二叉搜索树实现的 map 或 set 查找时间复杂度是 O(logn) ，但是它保证了数据顺序性

提示

例如 Java 中的 TreeMap 和 SortedMap

哈希查找表用一个哈希函数将 key 分配到不同的桶（bucket，也就是数组的不同 index）。这样，开销主要在哈希函数的计算以及数组的常数访问时间。在很多场景下，哈希查找表的性能很高。哈希查找表一般会存在 “碰撞” 的问题，就是说不同的 key 被哈希到了同一个 bucket。一般有几种应对方法：链表法，搜索树法和开放地址法。

链表法：将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。
搜索树法：一般采用自平衡搜索树，包括：AVL 树，红黑树。
开放地址法：则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。

Go map 的底层实现

和 map 相关的操作主要是：

增加一个 k-v 对 —— Add or insert；
删除一个 k-v 对 —— Remove or delete；
修改某个 k 对应的 v —— Reassign；
查询某个 k 对应的 v —— Lookup；

在源码中，表示 map 的结构体是 hmap，它是 hashmap 的“缩写”：

// A header for a Go map.
type hmap struct {
    // 元素个数，调用 len(map) 时，直接返回此值
    count     int
    flags     uint8
    // buckets 的对数 log_2
    B         uint8
    // overflow 的 bucket 近似数
    noverflow uint16
    // 计算 key 的哈希的时候会传入哈希函数
    hash0     uint32
    // 指向 buckets 数组，大小为 2^B
    // 如果元素个数为0，就为 nil
    buckets    unsafe.Pointer
    // 等量扩容的时候，buckets 长度和 oldbuckets 相等
    // 双倍扩容的时候，buckets 长度会是 oldbuckets 的两倍
    oldbuckets unsafe.Pointer
    // 指示扩容进度，小于此地址的 buckets 迁移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

说明一下，B 是 buckets 数组的长度的对数，也就是说 buckets 数组的长度就是 2^B。bucket 里面存储了 key 和 value。 buckets 是一个指针，最终它指向的是一个结构体：

type bmap struct {
    tophash [bucketCnt]uint8
}

但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置）。

来一个整体的图：

20230428145105

bmap 是存放 k-v 的地方，我们把视角拉近，仔细看 bmap 的内部组成。

20230428145300

上图就是 bucket 的内存模型，HOB Hash 指的就是 top hash。注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。

例如，有这样一个类型的 map：

map[int64]int8

如果按照 key/value/key/value/... 这样的模式存储，那在每一个 key/value 对之后都要额外 padding 7 个字节；而将所有的 key，value 分别绑定到一起，这种形式 key/key/.../value/value/...，则只需要在最后添加 padding。

每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来。

前言​

Go map 的底层实现​

Reference​

前言

Go map 的底层实现

Reference